import java.util.Arrays;

public class Loading {
    private static int n; // 集装箱数量
    private static int c; // 船的容量
    private static int[] w; // 集装箱重量数组
    private static int[] x; // 当前解
    private static int[] bestx; // 最优解
    private static int cw; // 当前载重量
    private static int r; // 当前剩余载重量
    private static int bestw; // 最优载重量

    public static void main(String[] args) {
        n = 5; // 集装箱数量
        c = 10; // 船的容量
        w = new int[]{2, 3, 4, 5, 6}; // 集装箱重量数组
        x = new int[n + 1]; // 当前解
        bestx = new int[n + 1]; // 最优解
        cw = 0; // 当前载重量
        bestw = 0; // 最优载重量
        r=0;

        loading(1);

        System.out.println("集装箱数组为： "+Arrays.toString(w));
        System.out.print("最优解：");
        for (int i = 1; i <= n; i++) {
            System.out.print(bestx[i] + " ");
        }
        System.out.println();
        System.out.print("最优载重量：" + bestw);
    }

    public static void loading(int i) {
        if (i > n) {
            for (int j = 1; j <= n; j++)
                System.out.print(x[j] + " ");
            System.out.println();

            if (cw > bestw) {
                for (int j = 1; j <= n; j++)
                    bestx[j] = x[j];
                bestw = cw;
            }
            return;
        }

//        r -= w[i];
        if (cw + w[i-1] <= c) {
            x[i] = 1;
            cw += w[i-1];
            loading(i + 1);
            x[i] = 0; //无论进入下一层与否都会执行，这是更为保险的选择
            cw -= w[i-1];
        }
        // 这是因为回溯算法需要考虑两种情况：一种是选择将第 i 个物品放入背包，另一种是不选择放入背包。
        // 因此，无论 if 条件是否成立，都需要递归调用 loading(i + 1)。
//        if (cw + r > bestw)
//        {
        loading(i + 1);
//        }
//        r += w[i];
    }
}
